KInterILP::KInterILP( const char* input_file ) : Algorithm( input_file ){
	R = 2*L;
	result = 0;
}

KInterILP::~KInterILP(){
}

void KInterILP::solve(){	
	IloEnv env;
	IloModel model(env);
	IloNumVarArray x(env);
	IloNumVarArray y(env);
	IloRangeArray constraints(env);
	
	//create variables x
	for (int i = 0; i < R; ++i) {
		x.add(IloNumVar(env, 0, 1, ILOINT));
	}
	
	//create variables y
	for (int i = 0; i < L; ++i) {
		y.add(IloNumVar(env, 0, 1, ILOINT));
	}
	
	//objective function
	IloObjective obj = IloMaximize(env);
	for (int i = 0; i < R; ++i) {
		obj.setLinearCoef(x[i], 1);
	}
	
	//constraint 1
	IloRange constraint1(env, k, k);
	for (int i = 0; i < L; ++i){
		constraint1.setLinearCoef(y[i], 1);
	}
	constraints.add(constraint1);
	
	//constraints 2
	for (int j = 0; j < L; ++j) {
		for (int i = 0; i < R; ++i) {
			if (!sets[j].has(i+1)) {
				IloRange constraint2(env, -IloInfinity, 1);
				constraint2.setLinearCoef(y[j], 1);
				constraint2.setLinearCoef(x[i], 1);
				constraints.add(constraint2);
			}
		}
	}
	
	model.add( constraints );
	model.add( obj );
	
	IloCplex cplex(model);
	
	cplex.setOut(env.getNullStream());
	
	cplex.setParam(IloCplex::TiLim,61);
	
	
	IloNumVarArray startVar(env);
	IloNumArray startVal(env);
	
	int xval[R];
	int yval[L];
	
	warmStart(xval,yval);
	
	for (int i = 0; i < R; ++i) {
		startVar.add(x[i]);
		startVal.add(xval[i]);
	}
	for (int i = 0; i < L; ++i) {
		startVar.add(y[i]);
		startVal.add(yval[i]);
	}
	
	
	cplex.addMIPStart(startVar, startVal);
	startVal.end();
	startVar.end();
	
	
	if (!cplex.solve()) {
		cout << "Error: the Integer Linear Model could not be solved." << endl;
		exit(-1);
	}
	
	IloNumArray chosen_elements(env);
	cplex.getValues(chosen_elements, x);
	
	IloNumArray chosen_sets(env);
	cplex.getValues(chosen_sets, y);
	
	for (int i = 0 ; i < R; ++i) {
		if (chosen_elements[i] ){
			++result;
		}
	}
	double time = cplex.getTime();
	cout << result;
	if (time > 60.0) {
		cout << "*";
	}
	cout << " " << time << endl;
}

void KInterILP::warmStart(int xval[], int yval[]){
	memset(xval,0,R*sizeof(int));
	memset(yval,0,L*sizeof(int));
	
	int is_in_solution[L];
	memset(is_in_solution,0,L*sizeof(int));
	
	Set intersection_set;
	int* s = new int[k];
	s[0] = 0;
	
	//escolhe o maior subconjunto para iniciar a solução s
	for(int i = 0; i < L; ++i)
		if(sets[i].cardinality() > sets[s[0]].cardinality())
			s[0] = i;
		
	is_in_solution[s[0]] = 1;
	
	intersection_set.union_(&sets[s[0]]);
	
	for(int i = 1; i < k; ++i){
		
		struct intersection_info intersection_cardinalities[L];
		memset(intersection_cardinalities,0,L*sizeof(struct intersection_info));
		
		for(int j = 0; j < L; ++j){
			intersection_cardinalities[j].id_set = j;
			intersection_cardinalities[j].cardinality = sets[j].cardinality();
			intersection_cardinalities[j].is_in_solution = is_in_solution[j];
			if(!is_in_solution[j]){
				Set* temp = Set::intersection(&intersection_set, &sets[j]);
				intersection_cardinalities[j].cardinality_after_intersection = temp->cardinality();
				delete temp;
			}
			else{
				intersection_cardinalities[j].cardinality_after_intersection = 0;
			}
		}
		
		qsort(intersection_cardinalities, L, sizeof(struct intersection_info), compareIntersectionInfo);
		
		for (int j = 0; j < L; ++j) {
			if (!is_in_solution[j]) {
				s[i] = j;
				is_in_solution[j] = 1;
				intersection_set.intersection( &sets[j] );
				break;
			}
		}
	}
	
	for (int i = 0; i < L; ++i) {
		yval[i] = is_in_solution[i];
	}
	
	int* intersection_array = intersection_set.getArray();
	for (int i = 0; i < intersection_set.cardinality(); ++i) {
		xval[intersection_array[i]-1] = 1;
	}
	delete [] intersection_array;
	
}



int KInterILP::getQualityOfBest(){
	return result;
}

